#include <postgres.h>
#include <funcapi.h>
#include <executor/spi.h>
#include <commands/trigger.h>
#include <utils/lsyscache.h>
#include <utils/typcache.h>
#include <utils/array.h>
#include <utils/varbit.h>
#include <catalog/pg_operator.h>

PG_MODULE_MAGIC;

/* Most of the following defines are taken from contrib/intarray/_int.h Note
** that this contrib is not required (but it's definately worth using).
*/

/* Dimension of array */
#define NDIM 1

/* Useful macros for accessing int4 arrays */
#define ARRPTR(x)  ( (int4*) ARR_DATA_PTR(x) )
#define ARRNELEMS(x)  ArrayGetNItems(ARR_NDIM(x), ARR_DIMS(x))

/* Reject arrays we can't handle; but allow a NULL or empty array */
#define CHECKARRVALID(x) \
    do { \
        if (x) { \
            if (ARR_NDIM(x) != NDIM && ARR_NDIM(x) != 0) \
                ereport(ERROR, \
                        (errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR), \
                         errmsg("array must be one-dimensional"))); \
            if (ARR_HASNULL(x)) \
                ereport(ERROR, \
                        (errcode(ERRCODE_NULL_VALUE_NOT_ALLOWED), \
                         errmsg("array must not contain nulls"))); \
        } \
    } while(0)

/* Checks for our definition of a void array. */
#define ARRISVOID(x)  ((x) == NULL || ARRNELEMS(x) == 0)

#define ARRAY_DATUM_FROM_ARG(X)          \
    PG_ARGISNULL(X) == true ? NULL :     \
    (ArrayType*)DatumGetPointer(PG_DETOAST_DATUM(PG_GETARG_DATUM(X)));


/*----------------------------------------------------------------------------*/
/* Utility functions                                                          */
/*----------------------------------------------------------------------------*/

/* Combine mode and id into a single 32 bit value. The high 3 bits will contain
** the mode, and the lower 29 bit will contain the id (uid/gid).
*/
static int32 create_priv(int32 id, int32 mode)
{
    int32 priv = mode;

    /* Shift mode to high 3 bits */
    priv = priv << 29;

    /* Clear high 3 id bits, AND with priv, putting it in lower 29 bits. */
    priv = priv | (id & 0x1FFFFFFF);

    return priv; 
}

/* Extracts the id (lower 29 bits) from a priv. */
static int32 priv_id(int32 priv)
{
    return priv & 0x1FFFFFFF;
}

/* Extracts the mode (high 3 bits) from a priv. */
static int32 priv_mode(int32 priv)
{
    return (priv >> 29) & 0x7;
}

/* Validates a priv mode. */
static int32 priv_mode_valid(int32 mode)
{
    if(mode > 8)
    {
        return false;
    }

    if(mode < 0)
    {
        return false;
    }

    return true;
}

/* Validates a priv id. */
static int32 priv_id_valid(int32 id)
{
    if(id > 0x20000000)
    {
        return false;
    }

    if(id < 0)
    {
        return false;
    }

    return true;
}

/* Takes an id and mode and validates them. If either file, it logs an error. */
static bool priv_valid(int32 id, int32 mode)
{
    if(priv_mode_valid(mode) == false)
    {
        elog(ERROR, "acl_priv(): invalid mode");

        return false;
    }

    if(priv_id_valid(id) == false)
    {
        elog(ERROR, "acl_priv(): invalid id");

        return false;
    }

    return true;
}

/* Compare function for qsort() to order ACLs by mode descending. */
static int32 cmp_priv(const void *aa, const void *bb)
{
    int32 id1 = priv_mode(*(const int32*)aa);
    int32 id2 = priv_mode(*(const int32*)bb);

    if(id1 < id2)
    {
        return 1;
    }

    if(id1 > id2)
    {
        return -1;
    }
    
    return 0;
}

static int32 find_max_mode( int32* ids,   int32 idlist_len, 
                            int32* privs, int32 privlist_len )
{
    int32 id, i, j, mode, m, priv;

    /* Iterate through all gids. */
    for(i=0; i < idlist_len; i++)
    {
        /* Get next gid. */
        id = ids[i];
        
        /* Iterate through all group privs. */
        for(j=0; j < privlist_len; j++)
        {
            /* Get the group priv. */
            priv = privs[j];
            
            /* If the gid matches */
            if(priv_id(priv) == id)
            {
                /* Get the mode. */
                m = priv_mode(priv); 
                
                /* If its greater than the current. */
                if(m > mode)
                {
                    /* Assign it. */
                    mode = m;
                    
                    if(mode == 7)
                    {
                        /* As high as we can get. No need to read any more. */
                        return mode;
                    }
                }
            }
        }
    }
    
    return mode;
}

/* Creates a new integer array. */
static ArrayType* new_array(int32 num)
{
    ArrayType  *r;
    int32 nbytes = ARR_OVERHEAD_NONULLS(NDIM) + sizeof(int32)*num;

    r = (ArrayType*)palloc0(nbytes);

    SET_VARSIZE(r, nbytes);
    ARR_NDIM(r) = NDIM;
    r->dataoffset = 0;
    ARR_ELEMTYPE(r) = INT4OID;
    *((int32*) ARR_DIMS(r)) = num;
    *((int32*) ARR_LBOUND(r)) = 1;

    return r;
}

/*----------------------------------------------------------------------------*/
/* PG functions                                                               */
/*----------------------------------------------------------------------------*/

/* Adds a priv to an ACL. Arguments 
** 
** 1. ACL (integer[])
** 2. id  (integer)
** 3. mode (integer)
**
** Creates a priv from the id/mode arguments and adds it to the list. If there
** is a priv for the given id already in the list, it replaces it with the new
** priv.
**
** Returns the new/modified array.
*/

PG_FUNCTION_INFO_V1(acl_priv_set);

Datum acl_priv_set(PG_FUNCTION_ARGS)
{
    ArrayType *acl, *result;
    int32 size, id, mode, *privs;

    acl  = ARRAY_DATUM_FROM_ARG(0)
    id   = PG_GETARG_INT32(1);
    mode = PG_GETARG_INT32(2);

    /* Check that priv is valid */
    if(priv_valid(id, mode) == false)
    {
        /* Not valid, return the original array. Error was logged in the
        ** check.
        */
        return PG_GETARG_DATUM(0);
    }

    /* If the array is empty */
    if(ARRISVOID(acl) == true)
    {
        /* Create an array with 1 element, populate it, and return it */
        result   = new_array(1);
        privs    = ARRPTR(result);
        privs[0] = create_priv(id, mode);

        PG_RETURN_POINTER(result);
    }

    /* Array is not empty. Check it */
    CHECKARRVALID(acl);
    
    /* Get size and int32* pointer */
    size  = ARRNELEMS(acl);
    privs = ARRPTR(acl);
    
    /* Search through it looking for matching id. */
    int32 i;
    for(i = 0; i < size; i++)
    {
        if(priv_id(privs[i]) == id)
        {
            /* Already has an element with this id. Change it in place. Return
            ** the modified array.
            */
            privs[i] = create_priv(id, mode);

            /* Sort descending by mode to optimize search performance. */
            qsort(privs, size, sizeof(int32), cmp_priv);

            PG_RETURN_POINTER(acl);
        }
    }

    /* Element does not exist. Need to enlarge array and add this entry. */

    /* Create new array */
    result = new_array(size + 1);

    /* Copy contents of original array */
    memcpy(ARRPTR(result), ARRPTR(acl), size*sizeof(int32));

    /* Get ref to new array */
    privs = ARRPTR(result);
   
    /* Update size to take new/larger array into account. */
    size++;

    /* Assign last element. */
    privs[size-1] = create_priv(id, mode);
    
    /* Sort descending by mode to optimize search performance. */
    qsort(privs, size, sizeof(int32), cmp_priv);

    /* Free temp memory from TOAST. */
    PG_FREE_IF_COPY(acl, 0);

    PG_RETURN_POINTER(result);
}

/* Removes a priv from an ACL. Arguments 
** 
** 1. id  (integer)
** 2. ACL (integer[])
**
** Removes the priv for the given id from the ACL, if there is one.
**
** Returns the new/modified array.
*/

PG_FUNCTION_INFO_V1(acl_priv_remove);

Datum acl_priv_remove(PG_FUNCTION_ARGS)
{
    int32 id, size, *privs, *newprivs;
    ArrayType *acl, *result;

    /* Get arguments */
    acl = ARRAY_DATUM_FROM_ARG(0)
    id  = PG_GETARG_INT32(1);

    /* If the array is empty */
    if(ARRISVOID(acl) == true)
    {
        /* Return the argument */
        return PG_GETARG_DATUM(0);
    }

    /* Array is not empty. Check it. */
    CHECKARRVALID(acl);
    
    /* Get size and pointer to array. */
    size  = ARRNELEMS(acl);
    privs = ARRPTR(acl);
    
    /* Search through it looking for matching id. */
    int32 i;
    for(i = 0; i < size; i++)
    {
        if(priv_id(privs[i]) == id)
        {
            /* Found the item to remove. */

            /* Create new array one size smaller. */
            result   = new_array(size - 1);
            newprivs = ARRPTR(result);

            /* Iterate over orignal array. */
            int32 j = 0;
            int32 k = 0;
            for(j = 0; j < size; j++)
            {
                /* If the current element is not the element to remove. */
                if(j != i)
                {
                    /* Copy the priv over */
                    newprivs[k++] = privs[j];
                }
            }
            
            /* Sort descending by mode to optimize search performance. */
            qsort(newprivs, size-1, sizeof(int32), cmp_priv);
            
            /* Free temp memory from TOAST */
            PG_FREE_IF_COPY(acl, 0);
            
            PG_RETURN_POINTER(result);
        }
    }

    /* If we get this far, there was no match. Return the original array. */
    return PG_GETARG_DATUM(0);
}

PG_FUNCTION_INFO_V1(acl_privs);

/* Given an ACL, this function returns a result set containing the corresponding
** ids and modes for all privs in the list. The first column is the id, and
** second if mode. Most of this code is lifted straight from the docs.
*/

Datum acl_privs(PG_FUNCTION_ARGS)
{
    FuncCallContext *funcctx;
    int32 call_cntr;
    int32 max_calls;
    TupleDesc tupdesc;
    AttInMetadata *attinmeta;
    ArrayType* acl;

    acl = ARRAY_DATUM_FROM_ARG(0)

    /* Check array */
    CHECKARRVALID(acl);
    
    /* Stuff done only on the first call of the function. */
    if(SRF_IS_FIRSTCALL())
    {
        MemoryContext oldcontext;

        /* Create a function context for cross-call persistence */
        funcctx = SRF_FIRSTCALL_INIT();

        /* Switch to memory context appropriate for multiple function calls. */
        oldcontext = MemoryContextSwitchTo(funcctx->multi_call_memory_ctx);

        /* Total number of tuples to be returned */
        funcctx->max_calls = ARRNELEMS(acl);;

        /* Build a tuple descriptor for our result type */
        if(get_call_result_type(fcinfo, NULL, &tupdesc) != TYPEFUNC_COMPOSITE)
            ereport(ERROR,
                    (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
                     errmsg("function returning record called in context "
                            "that cannot accept type record")));

        /* generate attribute metadata needed later to produce tuples from raw C
        ** strings
        */

        attinmeta = TupleDescGetAttInMetadata(tupdesc);
        funcctx->attinmeta = attinmeta;

        MemoryContextSwitchTo(oldcontext);
    }

    /* Stuff done on every call of the function */
    funcctx = SRF_PERCALL_SETUP();

    call_cntr = funcctx->call_cntr;
    max_calls = funcctx->max_calls;
    attinmeta = funcctx->attinmeta;
 
    /* Do when there is more left to send */
    if(call_cntr < max_calls)
    {
        char       **values;
        HeapTuple    tuple;
        Datum        result;

        int32* privs = ARRPTR(acl);

        /* Prepare a values array for building the returned tuple.  This should
        ** be an array of C strings which will be processed later by the type
        ** input functions.
        */
        values    = (char**)palloc( 2 * sizeof(char*));
        values[0] =  (char*)palloc(16 * sizeof(char));
        values[1] =  (char*)palloc(16 * sizeof(char));

        snprintf(values[0], 16, "%d", priv_id(privs[call_cntr]));
        snprintf(values[1], 16, "%d", priv_mode(privs[call_cntr]));

        /* Build a tuple */
        tuple = BuildTupleFromCStrings(attinmeta, values);

        /* Make the tuple into a datum */
        result = HeapTupleGetDatum(tuple);

        /* Clean up (this is not really necessary) */
        pfree(values[0]);
        pfree(values[1]);
        pfree(values);

        SRF_RETURN_NEXT(funcctx, result);
    }
    else
    {
        /* No more left */
        SRF_RETURN_DONE(funcctx);
    }
}

/* This function creates an ACL priv integer given a id (uid/gid) and a UNIX
** mode.
** 
** Arguments:
**
** 1. id (integer)
** 2. mode (integer)
**
** Returns the corresponding priv (integer).
*/

PG_FUNCTION_INFO_V1(acl_priv);

Datum acl_priv(PG_FUNCTION_ARGS)
{
    int32 id   = PG_GETARG_INT32(0);
    int32 mode = PG_GETARG_INT32(1);

    if(priv_valid(id, mode) == false)
    {
        return PointerGetDatum(NULL);
    }

    PG_RETURN_INT32(create_priv(id, mode));
}

/* This function computes the id within a priv integer.
**
** Arguments:
**
** 1. priv (integer)
**
** Returns returns the id within a priv integer.
*/

PG_FUNCTION_INFO_V1(acl_id);

Datum acl_id(PG_FUNCTION_ARGS)
{
    int32 priv  = PG_GETARG_INT32(0);

    PG_RETURN_INT32(priv_id(priv));
}

/* This function computes the mode within a priv integer.
**
** Arguments:
**
** 1. priv (integer)
**
** Returns returns the mode within a priv integer.
*/

PG_FUNCTION_INFO_V1(acl_mode);

Datum acl_mode(PG_FUNCTION_ARGS)
{
    int32 priv  = PG_GETARG_INT32(0);

    PG_RETURN_INT32(priv_mode(priv));
}

/* This is the main function in the library. It computes the highest mode for a
** given user/group list for a given group ACL and user ACL.
**
** Arguments:
**
** 1. uid (integer)
** 2. gids (integer[])
** 3. user ACL (integer[])
** 4. group ACL (integer[])
**
** Returns returns the highest mode for the user.
*/

PG_FUNCTION_INFO_V1(acl_access);

Datum acl_access(PG_FUNCTION_ARGS)
{
    ArrayType *glist, *uacl, *gacl;
    int32 uid, tmpmode, mode=0;

    /* Get the arguments. */
    uid   = PG_GETARG_INT32(0);
    glist = ARRAY_DATUM_FROM_ARG(1)
    uacl  = ARRAY_DATUM_FROM_ARG(2)
    gacl  = ARRAY_DATUM_FROM_ARG(3)

    /* Check arrays */
    CHECKARRVALID(glist);
    CHECKARRVALID(uacl);
    CHECKARRVALID(gacl);

    /* Start with groups first. We have a higher probability of getting a hit on
     * groups than on users. */

    /* If there is a gidlist provided, and there is a non-empty group ACL */
    if((ARRISVOID(glist) == false) && (ARRISVOID(gacl) == false))
    {
        /* Check all gids in the gidlist with the ACL and find the highest mode. */
        mode = find_max_mode( ARRPTR(glist), ARRNELEMS(glist), 
                              ARRPTR(gacl), ARRNELEMS(gacl) );

        if(mode == 7)
        {
            return mode;
        }
    }

    /* If there is a non-empty user ACL */
    if(ARRISVOID(uacl) == false)
    {
        /* Check all gids in the gidlist with the ACL and find the highest mode. */
        tmpmode = find_max_mode(&uid, 1, ARRPTR(uacl), ARRNELEMS(uacl));

        if(tmpmode > mode)
        {
            mode = tmpmode;
        }
    }

    PG_RETURN_INT32(mode);
}

/* This function is similar or acl_access(). It is a slight optimization in that
** you can provide a minimum mode that must be found, and if found, it will to
** quit reading and return true. If the minimum is not found, it returns false.
**
** Arguments:
**
** 1. uid (integer)
** 2. gids (integer[])
** 3. minumum mode (integer)
** 4. user ACL (integer[])
** 5. group ACL (integer[])
**
** Returns returns the highest mode for the user.
*/

PG_FUNCTION_INFO_V1(acl_min);

Datum acl_min(PG_FUNCTION_ARGS)
{
    ArrayType *glist, *uacl, *gacl;
    int32 uid, min_mode, mode = 0;

    /* Get the arguments. */
    uid      = PG_GETARG_INT32(0);
    glist    = ARRAY_DATUM_FROM_ARG(1)
    min_mode = PG_GETARG_INT32(2);
    uacl     = ARRAY_DATUM_FROM_ARG(3)
    gacl     = ARRAY_DATUM_FROM_ARG(4)

    /* Check arrays */
    CHECKARRVALID(glist);
    CHECKARRVALID(uacl);
    CHECKARRVALID(gacl);

    /* Start with groups first. We have a higher probability of getting a hit on
     * groups than on users. */

    /* If there is a gidlist provided, and there is a non-empty group ACL */
    if((ARRISVOID(glist) == false) && (ARRISVOID(gacl) == false))
    {
        /* Check all gids in the gidlist with the ACL and find the highest mode. */
        mode = find_max_mode( ARRPTR(glist), ARRNELEMS(glist), 
                              ARRPTR(gacl), ARRNELEMS(gacl) );

        if(mode >= min_mode)
        {
            PG_RETURN_BOOL(true);
        }
    }

    /* If there is a non-empty user ACL */
    if(ARRISVOID(uacl) == false)
    {
        /* Check all gids in the gidlist with the ACL and find the highest mode. */
        mode = find_max_mode(&uid, 1, ARRPTR(uacl), ARRNELEMS(uacl));

        if(mode >= min_mode)
        {
            PG_RETURN_BOOL(true);
        }
    }

    PG_RETURN_BOOL(false);
}
